package newcoder_exp.justPractise;
import java.util.*;
import org.junit.*;
//找到字符串的所有排列，按字典序
public class NC121 {
    public class Solution {
        public ArrayList<String> Permutation(String str) {
            if (str == null || str.length() == 0) return new ArrayList<>();
            char[] ss = str.toCharArray();
            dfs(0, ss);
            ArrayList<String> result = new ArrayList<>();
            while (!res.isEmpty()) {
                result.add(res.poll());
            }
            return result;
        }

        Queue<String> res = new PriorityQueue<>((s1, s2) -> s1.compareTo(s2));
        public void dfs(int idx, char[] ss) {
            if (idx == ss.length) {
                res.add(new String(ss));
                return;
            }

            Set<Character> set = new HashSet<>();
            for (int i = idx; i < ss.length; i++) {
                if (!set.contains(ss[i])) { //包括自身也要算上，此次自己和自己交换
                    set.add(ss[i]);
                    swap(i, idx, ss);
                    dfs(idx + 1, ss);
                    swap(i, idx, ss);
                }
            }
        }

        public void swap(int i , int j, char[] ss) {
            char t = ss[i];
            ss[i] = ss[j];
            ss[j] = t;
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        int[] nums = new int[]{};
       System.out.println( s.Permutation("abc"));;

       System.out.println("cba".compareTo("cab"));
    }


}
